package com.chunlin.priorityqueue;

import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.PriorityQueue;

public class PriorityQueueTest {
    public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {
//        test1();
//        test2();
        test3();
    }

    private static void test3() {
        int[] arr = {4,1,9,2,8,0,7,3,6,5};
        // 一般在创建优先级队列对象时，如果知道元素个数，建议就直接将底层容量给好
        // 否则在插入时需要可能需要扩容
        // 扩容机制：开辟更大的空间，拷贝元素，这样效率会比较低
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(arr.length);

        for (int e : arr) {
            //插入元素e，插入成功返回true，如果e对象为空，抛出NullPointerException异常，时间复杂度log2N，注意：空间不够时候会进行扩容
            priorityQueue.offer(e);
        }

        // 打印优先级队列中有效元素个数
        System.out.println(priorityQueue.size());
        // 获取优先级最高的元素
        System.out.println(priorityQueue.peek());

        // 从优先级队列中删除两个元素之后，再次获取优先级最高的元素
        priorityQueue.poll();
        priorityQueue.poll();
        System.out.println(priorityQueue.size());
        System.out.println(priorityQueue.peek());

        priorityQueue.offer(0);
        System.out.println(priorityQueue.peek());

        priorityQueue.clear();
        if (priorityQueue.isEmpty()) {
            System.out.println("优先级队列已经为空!");
        } else {
            System.out.println(priorityQueue.size());
        }

        //PriorityQueue底层数组的默认容量是11
        //扩容条件：当向 PriorityQueue 中添加元素且当前数组容量不足时，会触发扩容
        //扩容策略：
        //如果当前容量小于 64，则新的容量是当前容量加 2
        //如果当前容量大于等于 64，则新的容量是当前容量的 1.5 倍（即 oldCapacity + (oldCapacity >> 1)）
        //保证新容量足够：确保新的容量至少满足传入的 minCapacity 要求,如果上面扩大后的容量依然不够的话,那么就直接使用minCapacity
        //最大数组大小限制：如果计算出的新容量超过了最大数组大小（MAX_ARRAY_SIZE），则会进行处理以防止内存溢出

    }

    private static void test2() {
        PQCompare pqCompare = new PQCompare();

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(pqCompare);
        priorityQueue.offer(4);
        priorityQueue.offer(3);
        priorityQueue.offer(2);
        priorityQueue.offer(1);
        priorityQueue.offer(5);
        //默认是小堆,我们实现了比较器之后就是大堆
        System.out.println(priorityQueue.peek());
    }

    //Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列
    // PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，主要学习PriorityQueue


    //关于PriorityQueue的使用要注意：
    //1. 使用时必须导入PriorityQueue所在的包，即：import java.util.PriorityQueue;
    //2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常
    //3. 不能插入null对象，否则会抛出NullPointerException
    //4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容
    //5. 插入和删除元素的时间复杂度为log2N
    //6. PriorityQueue底层使用了堆数据结构,PriorityQueue 的底层实现是一个数组，并且这个数组保持了堆的特性
    //7. PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素

    //优先级队列的构造
    private static void test1() throws IllegalAccessException, NoSuchFieldException {
        // 创建一个空的优先级队列，底层默认容量是11
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

        //创建一个空的优先级队列,底层的容量为100
        PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>(100);

        // 用ArrayList对象来构造一个优先级队列的对象
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(4);
        arrayList.add(3);
        arrayList.add(2);
        arrayList.add(1);

        PriorityQueue<Integer> priorityQueue2 = new PriorityQueue<>(arrayList);

        // 使用反射获取 PriorityQueue 的内部数组
        Field queueField = PriorityQueue.class.getDeclaredField("queue");
        queueField.setAccessible(true);
        Object[] queueArray = (Object[]) queueField.get(priorityQueue);
        Object[] queueArray2 = (Object[]) queueField.get(priorityQueue1);
        Object[] queueArray3 = (Object[]) queueField.get(priorityQueue2);

        System.out.println(priorityQueue);
        System.out.println(priorityQueue.size());
        System.out.println(queueArray.length);
        System.out.println(priorityQueue1);
        System.out.println(priorityQueue1.size());
        System.out.println(queueArray2.length);
        System.out.println(priorityQueue2);
        System.out.println(priorityQueue2.size());
        System.out.println(queueArray3.length);

        System.out.println(priorityQueue2.peek());
    }
}
